package com.cuz.hot100;

public class Q44wildcardMatch {
    //""
    //"******"
    public static void main(String[] args) {
        System.out.println(match("a", "aa"));
    }

    public static boolean match(String s1, String s2) {
        int s2Len = s2.length();
        int s1Len = s1.length();
        if (s1Len == 0 && s2Len != 0) {
            return false;
        }
        if (s2Len == 0) {
            if (s1Len == 0) {
                return true;
            }
            if (s1.charAt(0) != '*') {
                return false;
            }
            return match(s1.substring(1), s2);
        }
        char s1FirstChar = s1.charAt(0);
        char s2FirstChar = s2.charAt(0);
        if (s1FirstChar == s2FirstChar || s1FirstChar == '?') {
            return match(s1.substring(1), s2.substring(1));
        }
        if (s1FirstChar == '*') {
            return match(s1, s2.substring(1))
                    || match(s1.substring(1), s2);
        }
        return false;
    }

    public static boolean match2(String s1, String s2) {
        int s2Len = s2.length();
        int s1Len = s1.length();
        if (s1Len == 0 && s2Len == 0) {
            return true;
        }
        if (s1Len == 0) {
            return false;
        }
        if (s2Len == 0) {
            return false;
        }
        boolean[][] dp = new boolean[s1Len + 1][s2Len + 1];
        dp[0][0] = true;
        for (int i = 1; i < s1Len; i++) {
            if (s1.charAt(i) == '*') {
                dp[i][0] = true;
            }
        }
        for (int i = 1; i <= s1Len; i++) {
            for (int j = 1; j < s2Len; j++) {
                if (s1.charAt(i) == '?' || s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                if (s1.charAt(i) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        return dp[s1Len][s2Len];
    }

}
